// //! /usr/bin/env python
// n
// // -*- coding: utf-8 -*-
// // vim:fenc=utf-8
// //
// // Copyright © 2020 crane <crane@crane-pc>
// //
// // Distributed under terms of the MIT license.

package main

import (
	"fmt"
)

func topk(nums []int, k int) []int {
	if len(nums) < k {
		return nums
	}

	quick_select(nums, k)

	return nums[:k]
}

// // 递归 quick_select: top(k) 放到nums[:k]
func quick_select(nums []int, k int) {
	fmt.Println(nums, k)
	if len(nums) < k {
		panic("nums len less than k")
	}

	pivot_idx := get_pivot_idx(nums)
	left_idx := split(nums, pivot_idx)

	//fmt.Println("debug:", " left", left_idx, " nums:", nums, ", pivot:", pivot_num, ", pivot_idx", pivot_idx)
	// fmt.Println("debug:", " left", left_idx, " nums:", nums, ", pivot_idx", pivot_idx)
	// fmt.Println()
	if left_idx == k || left_idx-1 == k {
		return
	}

	if left_idx < k {
		// 要选5个, 只获取到top 3
		// NOTE: 注意这里虽然传入了nums[:] 分片, 但是递归中对于分片的修改,
		//       依然会体现在最初的nums数组中. 这是和python最大的区别, python中
		//       对于分片的修改, 会重新赋值一个list出来!
		quick_select(nums[left_idx:], k-left_idx)
	} else {
		// 要选5个, 但是获取到了top 6
		// 讲解问题为: 从top 6 中获取top5
		quick_select(nums[:left_idx-1], k)
	}
}

func split(nums []int, pivot_idx int) (left_idx int) {
	pivot_num := nums[pivot_idx]

	// pivot放到最后一位, 这样交换完毕后pivot刚好处于中枢位置.
	nums_l := len(nums)
	nums[pivot_idx], nums[nums_l-1] = nums[nums_l-1], nums[pivot_idx]

	left_idx = 0
	for idx := 0; idx < len(nums); idx++ {
		if nums[idx] >= pivot_num {
			nums[left_idx], nums[idx] = nums[idx], nums[left_idx]
			left_idx += 1
		}
	}

	if nums[left_idx-1] != pivot_num {
		panic("split must failed because of logic error!")
	}

	return left_idx
}

func get_pivot_idx(nums []int) int {
	return 0
}

func main() {
	arrays := []int{1, 2, 9, 8, 10, 3, 7, 0, 11}
	ret := topk(arrays, 3)
	fmt.Println(ret)
}
